<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: ArrayList.php 14 2006-11-28 22:05:19Z rdff3 $
 */
/**
 *
 */
require_once( "util/AbstractList.php" );
require_once( "util/RandomAccess.php" );

/**
 * ArrayList
 * 
 * Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, 
 * including null. 
 * 
 * The size, isEmpty, get, set, iterator, and listCollectionIterator operations run in constant time. The add operation runs in amortized 
 * constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). 
 * The constant factor is low compared to that for the LinkedList implementation.
 *  
 * The iterators returned by this class's iterator and listCollectionIterator methods are fail-fast: if list is structurally modified at 
 * any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator 
 * will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly 
 * and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
 * 
 * Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any 
 * hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw 
 * ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on 
 * this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
 * 
 * This class is a member of the PHP Collections Framework.  
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: ArrayList.php 14 2006-11-28 22:05:19Z rdff3 $
 */
class ArrayList extends AbstractList implements Llist, RandomAccess {

	private static $NOT_FOUND = -1;
	private $items = array();
	private $size;
	
	/**
	 * Construct an empty list.
	 */
	public function __construct() {
		parent::__construct();
		$this->clear();
	}
	
	/**
	 * Appends the specified element to the end of this list.
	 *
	 * @param Object $o element to be appended to this list
	 * @returns boolean true (as per the general contract of Collection.add).
	 */
	public function add( Object $o ) {
		$this->items[$this->size++] = $o;
		$this->mod_count++;
		return true;
	}
	
	/**
	 * Inserts the specified element at the specified position in this list.
	 * 
	 * Inserts the specified element at the specified position in this list. Shifts the element currently at that position 
	 * (if any) and any subsequent elements to the right (adds one to their indices).
	 *
	 * @param int $index index at which the specified element is to be inserted.
	 * @param Object $o element to be inserted
	 * @throws {@link IndexOutOfBoundsException} - if the index is out of range (index < 0 || index > size()).
	 */
	public function addAt( $index, Object $o ) {
		if ( $index < 0 or $index > $this->size() )
			throw new IndexOutOfBoundsException();
			
		$stop_size = $this->size() - 1;
		for ($i = $stop_size; $i >= $index; $i--) {
			$this->items[$i+1] = $this->items[$i];
		}
		
		$this->items[$index] = $o;
		$this->mod_count++;
		$this->size++;
	}
	
	/**
	 * Appends all of the elements in the specified Collection to the end of this list.
	 *
	 * Appends all of the elements in the specified Collection to the end of this list, in the order that they are returned 
	 * by the specified Collection's CollectionIterator. The behavior of this operation is undefined if the specified Collection is modified 
	 * while the operation is in progress. (This implies that the behavior of this call is undefined if the specified Collection 
	 * is this list, and this list is nonempty.)
	 *
	 * @param Collection $c the elements to be inserted into this list.
	 * @returns boolean true if this list changed as a result of the call
	 * @throws {@link NullPointerException} - if the specified collection is null.
	 * @see AbstractCollection::add()
	 */
	public function addAll( Collection $c ) {
		if (is_null($c) )
			throw new NullPointerException();
			
		$return_value = false;	
		$iterator = $c->iterator();
		while( $iterator->hasNext() ) {
			$return_value = $this->add( $iterator->getNext() );
		}
		return $return_value;
	}
	
	/**
	 * Inserts all of the elements in the specified Collection into this list, starting at the specified position.
	 *
	 * Inserts all of the elements in the specified Collection into this list, starting at the specified position. Shifts the 
	 * element currently at that position (if any) and any subsequent elements to the right (increases their indices). The new 
	 * elements will appear in the list in the order that they are returned by the specified Collection's iterator.
	 *
	 * @param int $index index at which the specified elements are to be inserted.
	 * @param Collection $c the elements to be inserted into this list.
	 * @returns boolean true if this list changed as a result of the call
	 * @throws {@link IndexOutOfBoundsException} - if the index is out of range (index < 0 || index > size()).
	 * @throws {@link NullPointerException} - if the specified collection is null.
	 */
	public function addAllAt( $index, Collection $c ) {
		if ( $index < 0 or $index > $this->size() )
			throw new IndexOutOfBoundsException();
		if (is_null($c) )
			throw new NullPointerException();
			
		$return_value = false;	
		$c_iterator = $c->iterator();
		while ($c_iterator->hasNext() ) {
			$this->addAt( $index++, $c_iterator->getNext() );
			$return_value = true;
		}
		return $return_value;
	}
	
	/**
	 * Removes all of the elements from this list. The list will be empty after this call returns.
	 */
	public function clear() {
		$this->size = 0;
		$this->items = array();
		$this->mod_count++;
	}
	
	/**
	 * Returns true if this list contains the specified element.
	 *
	 * @param Object $elem element whose presence in this List is to be tested.
	 * @returns boolean true if the specified element is present, false otherwise.
	 */
	public function contains( Object $elem ) {
		if ( $this->findPos( $elem ) != self::$NOT_FOUND )
			return true;
		else
			return false;
	}
	
	/**
	 * Returns the element at the specified position in this list.
	 *
	 * @param int $index index of the element to return
	 * @returns Object the element at the specified position in this list.
	 * @throws {@link IndexOutOfBoundsException} - if index is out of range (index < 0 || index >= size()).
	 */
	public function get( $index ) { 
		if ( $index < 0 or $index >= $this->size() )
			throw new IndexOutOfBoundsException();
		
		return $this->items[$index];
	}
	
	
	/**
	 * Searches for the first occurence of the given argument, testing for equality using the equals method.
	 *
	 * @param Object $elem an object
	 * @returns int the index of the first occurence of the argument in this list; returns -1 if the object is not found
	 * @see Object::equals()
	 */
	public function indexOf( Object $elem ) {
		return $this->findPos( $elem );
	}
	
	/**
	 * Tests if this list has no elements
	 *
	 * @returns boolean true if this list contains no elements
	 */
	public function isEmpty() {
		return ($this->size() == 0);
	}
	
	/**
	 * Returns the index of the last occurence of the specified object in this list.
	 *
	 * @param Object $elem the element desired
	 * @returns int the index of the last occurence of the specified object in this list, returns -1 if the object is not found.
	 */
	public function lastIndexOf( Object $elem ) {
		return $this->findLastPos( $elem );
	}
	
	/**
	 * Removes a single instance of the specified element from this list, if it is present.
	 *
	 * More formally,  removes an element e such that (o==null ? e==null : o.equals(e)), if the list contains one or 
	 * more such elements. Returns true if the list contained the specified element (or equivalently, if the list changed 
	 * as a result of the call).
	 *
	 * @param Object $elem element to be removed from this list, if present.
	 * @returns boolean true if the list contained the specified element.
	 */
	public function remove( Object $elem ) {
		$pos = $this->findPos( $o );
		
		if ($pos == self::$NOT_FOUND)
			return false;
		else {
			$this->removeAt( $pos );
			return true;
		}
	}
	
	/**
	 * Removes the element at the specified position in this list.
	 *
	 * Removes the element at the specified position in this list. Shifts any subsequent elements to the left 
	 * (subtracts one from their indices).
	 *
	 * @param int $index index of the element to be removed.
	 * @returns Object the element that was removed from the list
	 * @throws {@link IndexOutOfBoundsException} - if index is out of range (index < 0 || index >= size()).
	 */
	public function removeAt( $index ) {
		if ( $index < 0 or $index >= $this->size() )
			throw new IndexOutOfBoundsException();
	
		$old = $this->items[$index];
		$stop_index = $this->size() - 1;
		
		for ($i = $index; $i < $stop_index; $i++) {
			$this->items[$i] = $this->items[$i + 1];
		}
		
		$this->size--;
		$this->mod_count++;
		return $old;
	}
	
	/**
	 * Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive.
	 * 
	 * Removes from this List all of the elements whose index is between fromIndex, inclusive and toIndex, exclusive. Shifts 
	 * any succeeding elements to the left (reduces their index). This call shortens the list by (toIndex - fromIndex) elements. 
	 * (If toIndex==fromIndex, this operation has no effect.)
	 * 
	 * @param int $from_index index of the element to be removed
	 * @param int $to_index index after last element to be removed
	 * @throws {@link IndexOutOfBoundsException} - if index is out of range (index < 0 || index >= size()).
	 */
	public function removeRange( $from_index, $to_index ) {
		if ($from_index < 0 or $to_index >= $this->size() )
			return new IndexOutOfBoundsException();
			
		for ($i = $from_index; $i < $to_index; $i++ ) {
			$this->removeAt($i);
		}
	}
	
	/**
	 * Replaces the element at the specified position in this list with the specified element.
	 *
	 * @param int $index index of the element to return.
	 * @param Object $elem element to be stored at the specified position.
	 * @returns Object the element previously at the specified position in this list.
	 * @throws {@link IndexOutOfBoundsException} - if index is out of range (index < 0 || index >= size()).
	 */
	public function set( $index, Object $elem ) {
		if ( $index < 0 or $index >= $this->size() )
			throw new IndexOutOfBoundsException();
			
		$old = $this->items[$index];
		$this->items[$index] = $elem;
		return $old;
	}
	
	/**
	 * Returns the number of elements in this list.
	 *
	 * @returns int the number of elements in this list.
	 */
	public function size() {
		return $this->size;
	}
	
	/**
	 * Returns an array containing all of the elements in this list in the correct order.
	 *
	 * @returns array an array containing all of the elements in this list in the correct order.
	 */
	public function toArray() {
		return $this->items;
	}
	
	private function findPos( Object $o ) {
		$size = $this->size();
		for ($i = 0; $i < $size; $i++ ) {
			if ($o == null) {
				if ($this->items[$i] == null)
					return $i;
			}
			else if ( $o->equals( $this->items[$i] ) )
				return $i;
		}
		
		return self::$NOT_FOUND;
	}
	
	private function findLastPos( Object $o ) {
		$stop_point = $this->size() - 1;
		for ($i = $stop_point; $i >= 0; $i-- ) {
			if ($o == null) {
				if ($this->items[$i] == null)
					return $i;
			}
			else if ( $o->equals( $this->items[$i] ) )
				return $i;
		}
		
		return self::$NOT_FOUND;
	}
}


?>